#include "mergesort.h"
#include <stdlib.h>

static void merge( int *a, int *b, int lo, int m, int hi )
{
    int i=lo, j=hi, k=lo;

    while( i<=m )
    {
        b[k++] = a[i++];
    }

    while( j>m )
    {
        b[k++] = a[j--];
    }

    i=lo, j=hi, k=lo;
    while( i<=j )
    {
        a[k++] = ( b[i]<b[j] ? b[i++] : b[j--] );

    }
}

static void sort(int *a, int *b, int lo, int hi)
{
    if( lo<hi )
    {
        int m = (lo+hi)/2;
        sort( a, b, lo, m );
        sort( a, b, (m+1), hi );
        merge( a, b, lo, m, hi );
    }
}

void mergesort( int *a, int lo, int hi)
{
    int *b = (int *) malloc( (hi+1)*sizeof(int) );
    sort( a, b, lo, hi );
    free(b);
}

